package practice_2025_9.practice_9_5;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    /**
     * 腐烂的橘子
     * @param grid
     * @return
     */
    public int orangesRotting(int[][] grid) {
        // 腐烂橘子相邻的新鲜橘子都会腐烂
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        // 是否有新鲜橘子
        boolean flg = false;
        // 查找存在的腐烂橘子
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    flg = true;
                }
            }
        }
        int count = 0;
        if (!flg) {
            return count;
        }
        while(!queue.isEmpty()) {
            int sz = queue.size();
            while(sz-- > 0) {
                int[] tmp = queue.poll();
                int x = tmp[0];
                int y = tmp[1];
                // 继续腐烂橘子
                for(int i = 0; i < dx.length; i++) {
                    int nextX = x + dx[i];
                    int nextY = y + dy[i];
                    if (nextX >= 0 && nextX < m
                             && nextY >= 0 && nextY < n
                             && grid[nextX][nextY] == 1) {
                                queue.add(new int[]{nextX, nextY});
                                grid[nextX][nextY] = 2;
                    }
                }
            }
            count++;
        }
        // 判断是否还有剩下的新鲜橘子
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return count - 1;
    }

    /**
     * 二叉树的右视图
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        // 每一层的最后一个节点
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return res;
        }
        queue.add(root);
        while(!queue.isEmpty()) {
            int sz = queue.size();
            while(sz-- > 0) {
                TreeNode node = queue.poll();
                if (sz == 0) {
                    res.add(node.val);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return res;
    }
}

